package com.mc.queue;

/**
 * @Description: 链式队列
 * @Author: MoChen
 */
public class HLinkQueue {

    private class LinkNode{
        int data;
        LinkNode next;

        public LinkNode(){}

        public LinkNode(int data) {
            this.data = data;
        }
    }

    private class LinkQueue{
        LinkNode front, rear;
    }

    private LinkQueue Q;

    // 初始化队列
    void initQueue(){
        // 初始时，front,rear都指向头结点
        Q.front = Q.rear = new LinkNode();
        // 不带头结点的话front和rear都要指向空
        Q.front.next = null;
    }

    // 判断队列是否为空
    boolean isEmpty(){
        return Q.front == Q.rear;
    }

    // 入队
    boolean enQueue(int x){
        LinkNode s = new LinkNode(x);
        s.next = null;
        // 如果不带头结点则front需要进行非空判断，为空则修改表头指针
        Q.rear.next = s; // 新结点挂到rear身上
        Q.rear = s; // 修改表尾指针
        return true;
    }

    // 出队
    boolean deQueue(){
        if(Q.rear == Q.front){ // 空队列
            return false;
        }
        LinkNode p = Q.front.next;
        Q.front.next = p.next; // 修改头结点的next指针
        if(Q.rear == p){ // 如果是最后一个结点
            Q.rear = Q.front;
        }
        return true;
    }
}
